// @algorithm @lc id=100303 lang=cpp
// @title shu-ju-liu-zhong-de-zhong-wei-shu-lcof
#include <iostream>
#include <queue>
using namespace std;
class MedianFinder {
public:
    // 前半列
    priority_queue<int, vector<int>, less<int>> maxHeap;
    // 后半列
    priority_queue<int, vector<int>, greater<int>> minHeap;

    MedianFinder() {}

    void addNum(int num) {
        if (maxHeap.size() == minHeap.size()) {
            maxHeap.push(num);
        }
        else {
            minHeap.push(num);
        }
        if (!maxHeap.empty() && !minHeap.empty()) {
            check();
        }
        return;
    }

    double findMedian() {
        double ans = 0;
        if (maxHeap.size() == minHeap.size()) {
            ans = ((double)maxHeap.top() + (double)minHeap.top()) / 2;
        }
        else {
            ans = maxHeap.size() > minHeap.size() ? (double)maxHeap.top() : (double)minHeap.top();
        }
        return ans;
    }

    void check() {
        while (maxHeap.top() > minHeap.top()) {
            int a = maxHeap.top();
            int b = minHeap.top();
            maxHeap.pop();
            minHeap.pop();
            maxHeap.push(b);
            minHeap.push(a);
        }
        return;
    }
};